package com.zxyankh.leetcode.question.chinese;

import java.util.Arrays;

/**
 * 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须原地修改，只允许使用额外常数空间。
 * <p>
 * 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
 * 1,2,3 → 1,3,2
 * 3,2,1 → 1,2,3
 * 1,1,5 → 1,5,1
 *
 * @author ankh
 * @since 16.05.2019
 */
public class No31 {

    public static void main(String[] args) {
        No31 no31 = new No31();
        no31.nextPermutation(new int[]{5, 4, 7, 5, 3, 2});
        System.out.println(1);
        no31.nextPermutation(new int[]{2, 3, 1});
        System.out.println(1);
        no31.nextPermutation(new int[]{1, 2, 3});
        System.out.println(1);
        no31.nextPermutation(new int[]{1, 3, 2});
        System.out.println(1);
        no31.nextPermutation(new int[]{3, 2, 1});
        System.out.println(1);
        no31.nextPermutation(new int[]{1, 1, 5});
        System.out.println(1);
        no31.nextPermutation(new int[]{1, 2, 3, 4});
        System.out.println(1);
        no31.nextPermutation(new int[]{});
    }

    /**
     * 1. 从后往前找，找到第一个降序的值，记录降序的值的index
     * 2. 将index后续的所有值按升序排序
     */
    public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums.length == 1) {
            return;
        }
        int index = 0;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i] > nums[i - 1]) {
                index = i;
                int tmp = nums[i];
                nums[i] = nums[i - 1];
                nums[i - 1] = tmp;
                break;
            }
        }
        int[] ns = new int[nums.length - index];
        for (int i = index, j = 0; i < nums.length; i++, j++) {
            ns[j] = nums[i];
        }
        Arrays.sort(ns);
        for (int i = index, j = 0; i < nums.length; i++, j++) {
            nums[i] = ns[j];
        }
    }

}
